Order-optimal consensus through randomized path averaging,” presented at

Abstract—Gossip algorithms have recently received significant attention, mainly because they constitute simple and robust mes-sage-passing schemes for distributed information processing over networks. However, for many topologies that are realistic for wire-less ad-hoc and sensor networks (like grids and random geometric graphs), the standard nearest-neighbor gossip converges as slowly as flooding messages). A recently proposed algorithm called geographic gossip improves gossip efficiency by a factor, by exploiting geographic information to enable multihop long-distance communications. This paper proves that a variation of geographic gossip that averages along routed paths, improves efficiency by an additional factor, and is order optimal ( messages) for grids and random geometric graphs with high prob-ability. We develop a general technique (travel agency method) based on Markov chain mixing time inequalities which can give bounds on the performance of randomized message-passing algo-rithms operating over various graph topologies. Index Terms—Average consensus, distributed algorithms, gossip algorithms, sensor networks. I